package sjp.demo.algorithm;

public class BagProblem {
    public static void main(String[] args) {
        int bagSpace = 6;
        int[] water = new int[]{1, 3, 10};
        int[] book = new int[]{2, 1, 3};
        int[] food = new int[]{3, 2, 9};
        int[] jeckit = new int[]{4, 2, 5};
        int[] camera = new int[]{5, 1, 6};
//        int[][] things = new int[][]{water, book};
        int[][] things = new int[][]{water, book, food, jeckit, camera};

        int[][] arr = new int[things.length][bagSpace];
        String[][] resultArr = new String[things.length][bagSpace];
        for (int i = 0; i < things.length; i++) {
            System.out.println("row##################################" + i);
            for (int j = 0; j < arr[i].length; j++) {
                System.out.println("当前空间============" + (j + 1));

                int space = j + 1;
                int id = things[i][0];
                int weight = things[i][1];
                int value = things[i][2];

                System.out.println("当前重量=" + weight);
                if (i == 0) {
                    if (weight <= space) {
                        arr[i][j] = value;
                        resultArr[i][j] = id + "";
                    }
                } else {

                    //上一个单元格的值
                    int previewMax = arr[i - 1][j];
                    // 当前商品价值 + 剩余空间的价值


                    if (weight <= space) {
                        int remain = space - weight;
                        System.out.println("当前剩余=" + remain);

                        if (remain > 0) {

                            int remainMax = arr[i - 1][remain - 1];
                            System.out.println("之前最大=" + resultArr[i - 1][remain - 1] + ":" + remainMax);

                            if (remainMax + value > previewMax) {
                                arr[i][j] = remainMax + value;
                                resultArr[i][j] = id + "+" + resultArr[i - 1][remain - 1];
                            } else {
                                arr[i][j] = previewMax;
                                resultArr[i][j] = resultArr[i - 1][j];
                            }

                        } else {
                            arr[i][j] = value;
                            resultArr[i][j] = id + "";
                        }
                    } else {
                        arr[i][j] = arr[i - 1][j];
                        resultArr[i][j] = resultArr[i - 1][j];
                    }
                }
                System.out.println("组合：" + resultArr[i][j]);
                System.out.println("最大价值：" + arr[i][j]);


            }
        }


    }
}
